home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / PROGRAMM / PASCAL / 0826.ZIP / SEARCH.ARC / SEARCHES.DOC < prev    next >
Text File  |  1987-10-27  |  4KB  |  77 lines
  1. { SEARCHES  --  A unit for rapidly searching a buffer for a string.
  2.  
  3.   Version 1.00 - 10/26/1987 - Initial release
  4.  
  5.   Scott Bussinger
  6.   Professional Practice Systems
  7.   110 South 131st Street
  8.   Tacoma, WA  98444
  9.   (206)531-8944
  10.   Compuserve 72247,2671
  11.  
  12.   This UNIT for Turbo Pascal version 4.0 provides contains high speed
  13. routines for searching buffers for strings.  To include this unit in your
  14. program add SEARCHES to the USES clause in your main program.
  15.   The unit actually has two routines which do the same thing in different
  16. ways.  The first is BlockPos which takes three parameters; a buffer
  17. containing the data be searched, the size of the buffer and the string to be
  18. searched for.  This routine is written in assembly language with inline code
  19. and is very fast since it takes advantage of special comparison instructions
  20. in the 8086 instruction set.  Note the the buffer is assumed to be based from
  21. a lower index of 1.  The result is the offset of the match within the buffer.
  22. A failure to match returns a 0.  This routine was originally written by Randy
  23. Forgaard for use with Turbo Pascal 3.0.
  24.   The second search routine is based on the Boyer-Moore search algorithm and
  25. is coded strictly in Pascal.  It is MUCH, MUCH slower than BlockPos and is
  26. included only because I felt like converting it and it doesn't hurt anything
  27. to include it in the unit.  Actually, the Boyer-Moore algorithm is quite a
  28. good search algorithm for some cases but doesn't do very well here because
  29. BlockPos is written in assembly language and BoyerMoore isn't.  I don't expect
  30. anyone will use this routine, but for those who want to, there are two steps
  31. to using the BoyerMoore routines.  The first is to process the search string
  32. into a special form for the actual search routine itself.  This procedure is
  33. called MakeBoyerTable and converts a string into a special record type called
  34. a BoyerTable.  This need only be done once for a given search string.  The
  35. second procedure is the search procedure itself and is called BoyerMoore.  For
  36. parameters, it takes the buffer containing data to be searched, the size of
  37. that buffer, the starting location in the buffer (in case you want to continue
  38. a previous search from where you left off), and the BoyerTable you created
  39. using MakeBoyerTable.  Again, the Buffer is assumed to be based from 1 and the
  40. result is the offset where the match was found (0 indicating not found).
  41. These routines are based on some routines written by Van Hall for Turbo Pascal
  42. 3.0 and I've included his original description of the Boyer-Moore algorithm in
  43. a separate file called BOYER.DOC for those who are interested.
  44.   Note that in general, the buffer can contain any data and the search string
  45. need not be text but rather any data in a string form.  For example, to search
  46. for a CR/LF sequence use #13#10 as the search string.
  47.   You can compile this file to create a test program using these routines.  It
  48. allows you to enter a search string and looks in this documentation file for
  49. the chosen string. }
  50.  
  51. program Test;
  52.  
  53. uses Searches;
  54.  
  55. var Buffer: array[1..maxint] of char;
  56.     Size: word;
  57.     Fyle: file;
  58.     Str: string;
  59.     Table: BoyerTable;
  60.  
  61. begin
  62. assign(Fyle,'SEARCHES.DOC');
  63. reset(Fyle,1);
  64. blockread(Fyle,Buffer,maxint,Size);
  65. close(Fyle);
  66. repeat
  67.   write('String to search for:');
  68.   readln(Str);
  69.  
  70.   writeln('  BlockPos = ',BlockPos(Buffer,Size,Str));
  71.  
  72.   MakeBoyerTable(Str,Table);
  73.   writeln('  BoyerMoore = ',BoyerMoore(Buffer,Size,1,Table))
  74.  
  75. until Str = ''
  76. end.
  77.